The present invention relates to integrated circuit memory devices and, more particularly, to content addressable memory (CAM) devices and methods of operating same.
In many memory devices, including random access memory (RAM) devices, data is typically accessed by supplying an address to an array of memory cells and then reading data from the memory cells that reside at the supplied address. However, in content addressable memory (CAM) devices, data is not accessed by initially supplying an address, but rather by initially applying data (e.g., search words) to the device and then performing a search operation to identify one or more entries within the CAM device that contain data equivalent to the applied data and thereby represent a xe2x80x9cmatchxe2x80x9d condition. In this manner, data is accessed according to its content rather than its address. Upon completion of the search operation, the identified location(s) containing the equivalent data is typically encoded to provide an address (e.g., CAM array block address+ row address within a block) at which the matching entry is located. If multiple matching entries are identified in response to the search operation, then local priority encoding operations may be performed to identify a location of a best or highest priority matching entry. Such priority encoding operations frequently utilize the relative physical locations of multiple matching entries within the CAM device to identify a highest priority matching entry. An exemplary CAM device that utilizes a priority encoder to identify a highest priority matching entry is disclosed in commonly assigned U.S. Pat. No. 6,370,613 to Diede et al., entitled xe2x80x9cContent Addressable Memory with Longest Match Detect,xe2x80x9d the disclosure of which is hereby incorporated herein by reference. The ""613 patent also discloses the use of CAM sub-arrays to facilitate pipelined search operations. Additional CAM devices are described in U.S. Pat. Nos. 5,706,224, 5,852,569 and 5,964,857 to Srinivasan et al. and in U.S. Pat. Nos. 6,101,116, 6,256,216, 6,128,207 and 6,262,907 to Lien et al., the disclosures of which are hereby incorporated herein by reference.
CAM cells are frequently configured as binary CAM cells that store only data bits (as xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d logic values) or as ternary CAM cells that store data bits and mask bits. As will be understood by those skilled in the art, when a mask bit within a ternary CAM cell is inactive (e.g., set to a logic 1 value), the ternary CAM cell may operate as a conventional binary CAM cell storing an xe2x80x9cunmaskedxe2x80x9d data bit. When the mask bit is active (e.g., set to a logic 0 value), the ternary CAM cell is treated as storing a xe2x80x9cdon""t carexe2x80x9d (X) value, which means that all compare operations performed on the actively masked ternary CAM cell will result in a cell match condition. Thus, if a logic 0 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 1 data bit, the compare operation will indicate a cell match condition. A cell match condition will also be indicated if a logic 1 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 0 data bit. Accordingly, if a data word of length N, where N is an integer, is applied to a ternary CAM array block having a plurality of entries therein of logical width N, then a compare operation will yield one or more match conditions whenever all the unmasked data bits of an entry in the ternary CAM array block are identical to the corresponding data bits of the applied search word. This means that if the applied search word equals {1011}, the following entries will result in a match condition in a CAM comprising ternary CAM cells: {1011}, {X011}, {1X11}, {10X1}, {101X}, {XX11}, {1XX1}), . . . , {1XXX}, {XXXX}.
FIG. 1 herein illustrates a conventional CAM device having a plurality of CAM array blocks therein arranged in a plurality of rows and columns. The CAM array blocks in the first, second, third and fourth rows are illustrated as CAM00-CAM07, CAM10-CAM17, CAM20-CAM27 and CAM30-CAM37. A respective row priority encoder is also provided between each pair of CAM array blocks. Thus, as illustrated, the CAM device of FIG. 1 includes sixteen (16) row priority encoders (shown as Row Priority Encoder00-Row Priority Encoder33). These row priority encoders perform final encoding of all match information generated by a respective pair of CAM array blocks. A respective global word line decoder is also provided for each row of CAM array blocks. As will be understood by those skilled in the art, each global word line decoder provides word line signals to the CAM array blocks of a respective row during reading and writing operations. These word line signals may be provided on global word lines. An exemplary row priority encoder is disclosed in U.S. Pat. No. 6,307,767 to Fuh.
Conventional techniques to reduce power consumption within CAM devices are disclosed in U.S. Pat. Nos. 6,191,969 and 6,191,970 to Pereira. In particular, the ""969 patent discloses a CAM array having CAM cells therein that include a discharge circuit connected between each cell and a fixed ground potential. Each of the discharge circuits include a control terminal coupled to receive a control signal indicative of the logical state of a match line segment in a respective row. These discharge circuits may be turned off to prevent discharge of respective match line segments during a search operation. U.S. Pat. No. 6,243,280 to Wong et al. also discloses a conventional technique to reduce power consumption by providing selective precharge of match line segments during a search operation. U.S. Pat. No. 5,517,441 to Dietz et al. discloses the use of inverters and pull-down transistors to pass match line signals from one match line segment to another match line segment during a search operation. U.S. Pat. Nos. 5,446,685 and 5,598,115 to Holst also disclose the use of rail-to-rail (i.e., Vdd-to-Vss) pulsed ground signals during search operations.
Notwithstanding these conventional techniques to reduce match line power consumption in partitioned CAM array blocks, there continues to be a need for techniques to further reduce power consumption in high capacity CAM devices having large numbers of CAM array blocks therein.
Content addressable memory (CAM) devices according to embodiments of the present invention conserve match line and bit line power when CAM array blocks therein are searched. These CAM array blocks are searched in a pipelined segment-to-segment manner to increase search speed. The pipelined search operations may also be interleaved with write and read operations in an efficient manner that reduces the occurrence of pipeline bubbles.
A CAM array according to an embodiment of the present invention includes a first plurality of rows CAM cells that are partitioned into at least two segments. These segments may include a xR segment and a xS segment. In some preferred embodiments, the xS segment may be longer than the xR segment. A match line control circuit is also provided. The match line control circuit may be disposed as a column of circuitry that extends between the xR and xS segments of the CAM array. In some embodiments, the match line control circuit includes a plurality of latches that are configured to receive a first plurality of match line signals developed in the xR segment during a xR search operation. The control circuit may also include boolean logic, which is electrically coupled to outputs of the plurality of latches. This boolean logic may be configured to evaluate match conditions determined by the plurality of match line signals and conserve power by selectively blocking discharge of at least one precharged pseudo-ground line segment in the xS segment of the CAM array during a xS search operation when the match conditions indicate that no matching entries are present in the first plurality of rows of CAM cells.
A content addressable memory (CAM) device according to another embodiment of the present invention includes a CAM array block having a first row of CAM cells therein. This first row may include first match line segment that is electrically coupled to a first segment of CAM cells in the first row and a second match line segment that is electrically coupled to a second segment of CAM cells in the first row. A pseudo-ground line segment that is electrically connected to the first and second segments of CAM cells may also be provided. The first row may also include a speed adjustable match line signal repeater. This match line signal repeater is configured to detect and propagate a miss signal transition from the first match line segment to the second match line segment during a search operation.
According to preferred aspects of these embodiments, the match line signal repeater is configured to propagate the miss signal transition in-sync with an active high-to-low transition of the pseudo-ground line segment from a maximum high voltage of (Vddxe2x88x92Vth) to a low voltage of Vss, where Vdd is a power supply voltage, Vth is a threshold voltage of an NMOS transistor and Vss is a ground reference voltage. The match line signal repeater may also include an inverter having an input that is electrically coupled to the first match line segment, an output and a sensitivity control terminal. To speed of the inverter in detecting a miss signal transition on the match line may be varied by including a voltage-controlled impedance element between the sensitivity control terminal of the inverter and a reference supply line. This element may be an NMOS bias transistor having a gate electrode that receives an adjustable N-bias voltage.
Additional embodiments of the present invention include methods of operating a content addressable memory (CAM) array. These methods may include writing a xR segment of a first row in the CAM array with a xR segment of a first write word while concurrently searching a xS segment of the same CAM array with a xS segment of a first search word. This step of writing a xR segment of a first row in the CAM array may be preceded by the step of searching a xR segment of the CAM array with a xR segment of the first search word. This step may also be followed by the step of searching the xR segment of the CAM array with a xR segment of a second search word while concurrently writing a xS segment of the first row with a xS segment of the first write word. Still further methods may include writing a xR segment of a first row in the CAM array with a xR segment of a first write word while concurrently writing a xS segment of a second row in the same CAM array.
According to additional embodiments of the present invention, a method of operating a CAM array may include precharging a first match line segment and a first pseudo-ground line segment associated with a row of CAM cells in the CAM array to maximum voltages of Vml and (Vmlxe2x88x92xcex1), respectively, during a precharge operation, where 0.1(Vml) less than xcex1 less than xc2xdVml. The row of CAM cells may then searched by switching the precharged first pseudo-ground line segment high-to-low and evaluating the first match line segment to determine whether a matching entry is present in the row of CAM cells. In further embodiments, the precharging step includes precharging the first pseudo-ground line segment through an NMOS pull-up transistor having a threshold voltage equal to Vth, where Vth equals xcex1, and Vml equals a power supply voltage (Vdd).
A pipelined search operation may also conserve bit line power by withholding application of second bits of a new search word to bit lines in the CAM array block until after at least one partial match has been detected between first bits of the new search word and the entries in the CAM array block. If at least one partial match is not detected within a respective segment of the CAM array block, the bit lines associated with the next higher segment are not actively driven with the corresponding bits of the new search word and the search operation terminates without discharging the match and pseudo-ground lines associated with the next higher segment(s). These operations are preferably performed on CAM array blocks having a logical width of xN bits. In some embodiments, one search word having a width of xN bits may be loaded into the CAM device in-sync with each leading edge of a clock signal. In other embodiments, search words of xN bits may be loaded into the CAM device on every leading and trailing edges of a clock signal.
According to a preferred aspect of another embodiment of the present invention, a CAM array block includes first bit lines associated with first columns in the CAM array block and second bit lines associated with second columns in the CAM array block and the search operation includes driving the first bit lines with the first bits of the new search while simultaneously applying bits of an old search word to the second bit lines by floating one or more of the second bit lines. The CAM array block may also include third bit lines associated with third columns therein and the search operation may include driving the first bit lines with the first bits of the new search word while simultaneously applying global mask bits to the third bit lines. An operation to apply global mask bits may include floating one or more of the third bit lines at a mask voltage level (e.g., logic 0 voltage level). The first columns may be arranged as a first plurality of consecutively ordered columns and the second and third columns may be collectively arranged as a second plurality of consecutively ordered columns. In particular, each of a plurality of rows in a CAM array block may be partitioned into a xL segment, a xM segment and a xN segment, where L, M and N are positive integers and L less than M less than N. In particular, L, M and N may be positive integers that meet the following requirement: 2Lxe2x89xa6M and 2Mxe2x89xa6N.